#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
        int min_insert_hori(const string &s)
        {
                int n = s.size();
                vector<vector<int>> dp(n, vector<int>(n, 0));
                for(int i = n - 2; i >= 0; i--){
                        for(int j = i + 1; j < n; j++){
                                if(s[i] == s[j]){
                                        dp[i][j] = dp[i + 1][j - 1];
                                }else{
                                        dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
                                }
                        }
                }
                return dp[0].back();
        }

        int min_insert_tilt(const string &s){
                int n = s.size();
                vector<vector<int>> dp(n, vector<int>(n, 0));
                for(int pos = 1; pos < n; pos++){
                        for(int l = 0, r = pos; r < n; l++, r++){
                                if(s[l] == s[r]){
                                        dp[l][r] = dp[l + 1][r - 1];
                                }else{
                                        dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1;
                                }
                        }
                }
                return dp[0].back();
        }

    public:
	int minInsertions(string s)
	{
                return min_insert_tilt(s);
	}
};

int main()
{
        string s = "mbadm";
        cout<<Solution().minInsertions(s)<<endl;
	return 0;
}